#include <stdio.h>
#include <stdlib.h>
#include "balaceTree.h"


tree_st *avlCreate()
{
	tree_st *root = NULL;
	char ch;
	while(1)
	{
		scanf("%c",&ch);
		if (ch == '#')
		{
			break;
		}
		avlInsert(&root,ch);
	}	
	return root;
}

void avlInsert(tree_st **root,Datatype data)
{
	if (*root == NULL)
	{
		tree_st *newnode = NULL;
		newnode = malloc(sizeof(*newnode));
		if (newnode == NULL)
		{
			fprintf(stderr,"malloc() faild!\n");
			exit(1);
		}
		newnode->data = data;
		newnode->count = 1;
		newnode->lchild = NULL;
		newnode->rchild = NULL;
		*root = newnode;
		return ;
	}
	if ((*root)->data > data)
	{
		avlInsert(&(*root)->lchild,data);

		if (avlDepth((*root)->lchild) - avlDepth((*root)->rchild) > 1)
		{
			if (data < (*root)->lchild->data)
			{
				*root = singleRight(*root);
			}
			else
			{
				*root = doubleWithLeftRight(*root);
			}	
		}
	}
	else if ((*root)->data < data)
	{
		avlInsert(&(*root)->rchild,data);

		if (avlDepth((*root)->rchild) - avlDepth((*root)->lchild) > 1)
		{
			if (data > (*root)->rchild->data)
			{
				*root = singleLeft(*root);
			}
			else
			{
				*root = doubleWithRightLeft(*root);
			}	
		}

	}
	else
	{
		(*root)->count++;
	}
	
}

tree_st *avlFind(tree_st *root,Datatype data)
{
	if (root == NULL)
	{
		return NULL;
	}
	
	if (root->data == data)
	{
		return root;
	}	
	if (root->data > data)
	{
		avlFind(root->lchild,data);
	}
	else
	{
		avlFind(root->rchild,data);
	}
}

int avlDepth(tree_st *root)
{
	if (root == NULL)
	{
		return 0;
	}
	return avlDepth(root->lchild) > avlDepth(root->rchild) ? avlDepth(root->lchild) + 1 : avlDepth(root->rchild) + 1;
}

static void drawTree_(tree_st *root,int level)
{
	if (root == NULL)
	{
		return ;
	}
	drawTree_(root->rchild,level + 1);
	for (int i = 0; i < level; i++)
	{
		printf("\t");
	}
	printf("%c\n",root->data);
	drawTree_(root->lchild,level + 1);
}

void drawTree(tree_st *root)
{
	drawTree_(root,0);
}

tree_st *singleLeft(tree_st *root)
{
	tree_st *k = root->rchild;
	root->rchild = k->lchild;
	k->lchild = root;
	return k;
}

tree_st *singleRight(tree_st *root)
{
	tree_st *k = root->lchild;
	root->lchild = k->rchild;
	k->rchild = root;
	return k;
}

tree_st *doubleWithLeftRight(tree_st *root)
{
	root->lchild = singleLeft(root->lchild);
	return singleRight(root);
}

tree_st *doubleWithRightLeft(tree_st *root)
{
	root->rchild = singleRight(root->rchild);
	return singleLeft(root);
}

void avlFirstShow(tree_st *root)
{
	if (root == NULL)
	{
		return ;
	}
	printf("%c ",root->data);
	avlFirstShow(root->lchild);
	avlFirstShow(root->rchild);
}

void avlMiddleShow(tree_st *root)
{
	if (root == NULL)
	{
		return ;
	}
	avlMiddleShow(root->lchild);
	printf("%c ",root->data);
	avlMiddleShow(root->rchild);
}

void avlLaterShow(tree_st *root)
{
	if (root == NULL)
	{
		return ;
	}
	avlLaterShow(root->lchild);
	avlLaterShow(root->rchild);
	printf("%c ",root->data);
}
